#include <iostream>
#include <vector>
#include <string>

using namespace std;

class MyLinkedList
{
public:
    MyLinkedList()
    {
        _dummyHead = new LinkedNode(0);
        _dummytail = new LinkedNode(0);
        _dummyHead->val = 0;
        _dummyHead->next = _dummytail;
        _dummytail->prev = _dummyHead;
    }

    int get(int index)
    {
        if (_dummyHead->val <= index || index < 0)
            return -1;
        LinkedNode *n = _dummyHead->next;
        while (index-- > 0)
            n = n->next;
        return n->val;
    }

    void addAtHead(int val)
    {
        LinkedNode *n = new LinkedNode(val);
        _dummyHead->next->prev = n;
        n->next = _dummyHead->next;
        n->prev = _dummyHead;
        _dummyHead->next = n;
        _dummyHead->val++;
        return;
    }

    void addAtTail(int val)
    {
        LinkedNode *n = new LinkedNode(val);
        _dummytail->prev->next = n;
        n->next = _dummytail;
        n->prev = _dummytail->prev;
        _dummytail->prev = n;
        _dummyHead->val++;
        return;
    }

    void addAtIndex(int index, int val)
    {
        if (index <= 0){
            addAtHead(val);
            return;
        }
        else if (_dummyHead->val < index)
            return;
        else if (_dummyHead->val == index){
            addAtTail(val);
            return;
        }
        LinkedNode *i = _dummyHead->next, *n = new LinkedNode(val);
        while (index-- > 0)
            i = i->next;
        i->prev->next = n;
        n->next = i;
        n->prev = i->prev;
        i->prev = n;
        _dummyHead->val++;
        return;
    }

    void deleteAtIndex(int index)
    {
        if (_dummyHead->val <= index || index < 0)
            return;
        LinkedNode *n = _dummyHead->next;
        while (index-- > 0)
            n = n->next;
        n->prev->next = n->next;
        n->next->prev = n->prev;
        delete n;
        _dummyHead->val--;
        return;
    }

private:
    struct LinkedNode
    {
        int val;
        LinkedNode *next;
        LinkedNode *prev;
        LinkedNode(int val) : val(val), next(nullptr), prev(nullptr) {}
    };
    LinkedNode *_dummyHead; // 链表长度保存在虚拟头节点的val中
    LinkedNode *_dummytail; // 虚拟尾节点
};

int main()
{
    MyLinkedList *obj = new MyLinkedList();
    obj->addAtHead(1);
    obj->addAtTail(3);
    obj->addAtIndex(1, 2);           // 链表变为1-> 2-> 3
    cout << obj->get(1) << endl;     // 返回2
    obj->deleteAtIndex(1);           // 现在链表是1-> 3
    cout << obj->get(1) << endl;     // 返回3
    return 0;
}
